package lcr;

import java.util.List;

public class Test0063 {
}

class Solution0063_1 {
    public String replaceWords(List<String> dictionary, String sentence) {
        Dict dict = new Dict();

        for (int i = 0; i < dictionary.size(); i++) {
            dict.insert(dictionary.get(i).toCharArray(), 0, i);
        }
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int replace = dict.replace(word.toCharArray(), 0);
            words[i] = replace == -1 ? word : dictionary.get(replace);
        }
        return String.join(" ", words);
    }

    class Dict{
        Dict[] next;
        int isWord;

        public Dict(){
            isWord = -1;
        }

        public void insert(char[] chars, int index,int flag){
            if (next == null) next = new Dict[26];
            Dict dict = next[chars[index] - 'a'];
            if (dict == null) {
                dict = new Dict();
                next[chars[index] - 'a'] = dict;
            }

            if (index == chars.length - 1){
                dict.isWord = flag;
            }else {
                dict.insert(chars, index + 1,flag);
            }
        }

        public int replace(char[] chars, int index){
            if (next == null||index == chars.length-1) return -1;
            Dict dict = next[chars[index] - 'a'];
            if (dict == null) return -1;

            if (dict.isWord != -1){
                return dict.isWord;
            }else {
                return dict.replace(chars,index+1);
            }
        }

    }
}
